/**
 * Max Heap based Priority Queue
 **/

#ifndef __prioheapH__
#define __prioheapH__

#include <vector>

namespace Rtl{

namespace BinaryHeapType {
	/// Ordering types
	/// Compare function returns true if A's priority greater than B.
	template <class tElem> struct MinHeap {
		inline static bool Compare(const tElem& a, const tElem& b) {
			return (a < b);
		};
	};

	template <class tElem> struct MaxHeap {
		inline static bool Compare(const tElem& a, const tElem& b) {
			return (b < a);
		};
	};
};


template <class tElem, class Order>
class BinaryHeap
{
protected:
	std::vector<tElem>	Queue;

	void Swap(int i, int j) {
		tElem tmp(Queue[i]);
		Queue[i] = Queue[j];
		Queue[j] = tmp;
	};

	void Heapify(int i){
		int max;
		
		//
		// Here we introduce some fudges to overcome
		// addressing of arrays starting from zero.
		// Take the first element (1) to be zero, and shift as so.
		//

		int ch = ((i + 1) * 2) - 1;
		
		if(ch >= Queue.size())
			return;
		if(Order::Compare(Queue[ch], Queue[i]))
			max = ch;
		else
			max = i;
		if(((ch + 1) < Queue.size())
			&& Order::Compare(Queue[ch+1], Queue[max]))
			max = ch+1;

		if(max != i){
			Swap(max, i);
			Heapify(max);
		};
	};

	void _Insert(int i){
		// Swap with parent node whilst prio greater
		while((i > 0) && Order::Compare(Queue[i], Queue[i/2])){
			Swap(i, i / 2);
			i = i / 2;
		};
	};

public:
	inline void Insert(const tElem& el){
		int n = Queue.size();
		Queue.push_back(el);
		_Insert(n);
	};

	/// Returns the element 
	inline const tElem& Get(int i) const{
		return Queue[i];
	};
	
	/// Removes an element from the heap and returns it.
	inline tElem Remove(int i){
		tElem x(Queue[i]);
		Queue[i] = Queue[Queue.size() - 1];
		Queue.pop_back();
		Heapify(i);
		return x;
	};

	inline void Clear() {
		Queue.clear();
	};

	inline int GetSize() const{
		return Queue.size();
	};

	inline bool IsEmpty() const {
		return Queue.empty();
	};
};


template <class TVal, class TPrio>
struct PriorityQueueItem
{
	typedef PriorityQueueItem<TVal,TPrio>	tThis;

	TVal	Value;
	TPrio	Priority;

	PriorityQueueItem(const TVal& x)
		: Value(x){};

	bool operator<(const tThis& pqi) const{
		return (Priority < pqi.Priority);
	};

	void operator= (const tThis &pqi){
		Value = pqi.Value;
		Priority = pqi.Priority;
	};

	operator TVal& (){
		return Value;
	};
	operator const TVal& () const{
		return Value;
	};

	void Swap(tThis &pqi){
		tThis t(pqi);
		pqi = *this;
		*this = t;
	};
};

template <class TVal, class Order = BinaryHeapType::MinHeap<PriorityQueueItem<TVal, int> > >
class PriorityQueue: public BinaryHeap< PriorityQueueItem<TVal, int>, Order > {

public:
	void Insert(const TVal& x, int p){
		BinaryHeap< PriorityQueueItem<TVal, int>, Order >::Insert(PriorityQueueItem<TVal, int>(x));
	};

	void IncreasePriority(int i, int p){
		this->Queue[i].Priority = p;
		this->_Insert(i);
	};

	const TVal& GetTop() const{
		return this->Queue[0];
	};

	TVal PopTop(){
		return this->Remove(0);
	};
};


}; // namespace

#endif
